template <const int P>
struct Combination {
	Combination(int n) : fac_(n + 1), inv_(n + 1) {
		fac_[0] = inv_[0] = 1;
		for (int i = 1; i <= n; i++) {
			fac_[i] = 1ll * i * fac_[i - 1] % P;
		}
		inv_[n] = power(fac_[n], P - 2);
		for (int i = n - 1; i >= 1; i--) {
			inv_[i] = 1ll * (i + 1) * inv_[i + 1] % P;
		}
	} 
	
	int power(int a, int b) {
		int result = 1;
		for (; b > 0; b >>= 1) {
			if (b & 1) {
				result = 1ll * result * a % P;
			}
			a = 1ll * a * a % P;
		}
		return result;
	}

	int C(int n, int m) {
		if (n < m || n < 0 || m < 0) {
			return 0;
		}
		return (int)(1ll * fac_[n] * inv_[m] % P * inv_[n - m] % P);
	}

	int A(int n, int m) {
		if (n < m || n < 0 || m < 0) {
			return 0;
		}
		return (int)(1ll * fac_[n] * inv_[n - m] % P);
	}

	vector<int> fac_, inv_;
};